Technical Field
The present invention relates to compression and, more particularly, to adaptive compression that changes compression methods based on output size thresholds.
Description of the Related Art
A goal of data compression is to compress an input to a smaller number of output bytes. However, in some applications, only outputs of certain sizes are used. For example, storage may be quantized in blocks (e.g., 512 bytes, 4 kilobytes, 64 kilobytes), where a block will take the same amount of physical space regardless of whether it is filled to capacity or stores only one byte of information. Current compressors do not adapt computation to coarsely quantized sizes of compressor output (and do not adapt to ensure that compression time/CPU constraints are likely to be met for arbitrary input data), leading to significant inefficiencies if compression is continued past the point where it is useful.
Some compressors are byte-oriented, and conventional adaptive compression is typically based on cost factors such as time, network bandwidth, or input/output cost. To the extent that any such techniques do consider output size as an element of their cost functions, the cost is determined as being proportional to the number of output bytes. Such adaptive compression techniques fail to account for discrete output size thresholds.
A number of compressors operate somewhat adaptively by performing an analysis phase on blocks of input data, arriving at pre-calculated functions of the input data. These outputs of the analysis phase are used to decide which of several compression schemes to invoke on the entire data block. Useful pre-calculated functions of the input data are efficiently computable, such as statistical estimation of entropy, or most frequently occurring, or simply the number of zero bytes. Thereafter, the previous approaches compress each block of data independently. One disadvantage of this approach is that the internal state of one compressor cannot easily be used to enhance the compression of an ensuing data block.